package heap;

import arrays.DynamicTOurOwnArray;

/**
 * @program: play-structure
 * @author: baichen
 * 使用动态数组实现最大堆，节点之间要有可比性，所以继承了Comparable
 * 最大堆其实是基于完全二叉树想象而成的
 **/
public class MaxHeap<E extends Comparable<E>> {
    private DynamicTOurOwnArray<E> data;

    private MaxHeap(int capacity) {
        data = new DynamicTOurOwnArray<>(capacity);
    }

    public MaxHeap() {
        data = new DynamicTOurOwnArray<>();
    }

    //Heapify的过程,从最后一个非叶子结点开始，不断进行元素下沉
    public MaxHeap(E[] arr) {
        data = new DynamicTOurOwnArray<>(arr);
        // 找到最后一个节点，然后在siftDown会根据最后一个节点找到其父节点
        for (int i = arr.length - 1; i >= 0; i--) {
            siftDown(i);    //元素下沉
        }
    }

    // 返回堆中的元素个数
    public int size() {
        return data.getSize();
    }

    // 返回一个布尔值, 表示堆中是否为空
    public boolean isEmpty() {
        return data.isEmpty();
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
    private int parent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("index-0 doesn't have parent.");
        }
        return (index - 1) / 2;
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
    private int leftChild(int index) {
        return index * 2 + 1;
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
    private int rightChild(int index) {
        return index * 2 + 2;
    }

    // 向堆中添加元素
    public void add(E e) {
        data.addLast(e);    //在元素最后添加,次数在数组里面的size会加一
//        节点对应的索引，因为是在最后添加的，索引是getSize-1
        siftUp(data.getSize() - 1);
    }

    //堆中上浮元素,参数是节点对应的索引,因为堆规定父节点要大于左右孩子节点的值
    private void siftUp(int k) {
        while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
            //K所在的父节点的值与K节点的值做比较，如果父亲元素更小的话，二者交换位置
            data.swap(k, parent(k)); //使用 swap 方法进行k与k父亲对应元素交换
            k = parent(k);      //元素上浮，所以从父节点开始
        }
    }

    // 看堆中的最大元素
    public E findMax() {
        if (data.getSize() == 0)
            throw new IllegalArgumentException("Can not findMax when heap is empty.");
        return data.get(0); //根据堆的性质,堆顶元素值最大
    }

    // 取出堆中最大元素(即堆顶元素)，先将堆顶元素跟数组中最后一个元素交换，然后再将其下沉
    public E extractMax() {
        E ret = findMax();
        data.swap(0, data.getSize() - 1);      //最大元素与最后的一个元素交换位置
        data.delLast();    //删掉最大元素
        siftDown(0);    //进行下沉操作，对应索引为0
        return ret;
    }

    //元素下沉操作,推出大的元素到堆顶
    private void siftDown(int k) {
        //k节点的左孩子的索引小于数组长度,k节点没有右孩子
        while (leftChild(k) < data.getSize()) {
            int j = leftChild(k);   // 在此轮循环中,data[k]和data[j]交换位置
            //j+1其实表示的是k这个索引对应的父节点的右孩子,所以下面是比较左右孩子节点的大小
            if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
                j++;//如果右孩子节点大于左孩子节点，则j++,其实存储的实际上是右孩子的索引
                // data[j] 是 leftChild 和 rightChild 中的最大值
            }
            //k 与孩子中最大元素j进行对比,因为其实上面其实是在比较左右孩子节点哪个比较大
            if (data.get(k).compareTo(data.get(j)) >= 0)
                break;
            data.swap(k, j);    //若 j>k,则交换二者位置
            k = j;  //进行下一轮循环
        }
    }

    // 取出堆中的最大元素(即堆顶)，并且替换成元素e, O(log n)
    public E replace(E e) {
        E ret = findMax();
        data.set(0, e);
        siftDown(0);
        return ret;
    }
}
